package ru.eas.structure;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Heap {
    private int childrenCount;
    private List<Integer> data = new ArrayList<Integer>();
    private Comparator<Integer> comparator;

    public Heap(int childrenCount, Comparator<Integer> comparator) {
        this.comparator = comparator;
        this.childrenCount = childrenCount;
    }

    public void insert(int value) {
        data.add(value);
        siftUp(data.size() - 1);
    }

    private void siftUp(int index) {
        if (index == 0) {
            return;
        }

        int parentIndex = getParentIndex(index);
        int parentValue = data.get(parentIndex);
        int indexValue = data.get(index);
        if (comparator.compare(parentValue, indexValue) > 0) {
            swap(index, parentIndex);
            siftUp(parentIndex);
        }
    }

    public int extract() {
        if (data.size() == 1) {
            return data.remove(0);
        }

        int result = data.get(0);
        int lastValue = data.get(data.size() - 1);
        data.remove(data.size() - 1);
        data.set(0, lastValue);
        siftDown(0);
        return result;
    }

    public void changePriority(int value) {
        if (data.size() == 0) {
            return;
        }
        int index = 0;
        for (int i = 1; i < data.size(); i++) {
            if (data.get(i) == value) {
                index = i;
                break;
            }
        }
        int parentIndex = getParentIndex(index);
        if (index != 0 && comparator.compare(data.get(parentIndex), data.get(index)) > 0) {
            siftUp(index);
        } else {
            siftDown(index);
        }
    }

    private void siftDown(int index) {
        int resultIndex = 0;
        int resultValue = Integer.MAX_VALUE;

        for (int i = 0; i < childrenCount; i++) {
            int childrenIndex = getChildrenIndex(index, i);
            if (childrenIndex < data.size()) {
                int childenValue = data.get(childrenIndex);
                if (comparator.compare(resultValue, childenValue) > 0) {
                    resultIndex = childrenIndex;
                    resultValue = childenValue;
                }
            }
        }
        if (comparator.compare(resultValue, data.get(index)) >= 0) {
            return;
        }
        swap(index, resultIndex);
        siftDown(resultIndex);
    }

    private void swap(int index1, int index2) {
        int value1 = data.get(index1);
        int value2 = data.get(index2);
        data.set(index1, value2);
        data.set(index2, value1);
    }

    private int getChildrenIndex(int parentIndex, int childrenNumber) {
        return childrenCount * parentIndex + childrenNumber + 1;
    }

    private int getParentIndex(int index) {
        return (index + childrenCount - 1) / childrenCount - 1;
    }

    public boolean isEmpty() {
        return data.size() <= 1;
    }
}
